{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 最大流的作业"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 26.1-1   \n",
    "证明：（反证法）    \n",
    "$\\because$显然可以在$G^{'}$构造出和$G$相等的流,新构造顶点的流入流出都等于被删去的原先边的流即可。   \n",
    "$\\therefore$若$G^{'}$和$G$中的最大流不相等，则必有$f_{maxG^{'}}>f_{maxG}$   \n",
    "但是，对于$f_{maxG^{'}}$的方案，因为新建的$x$节点非源非汇且有且仅有一条入边和一条出边，所以出入边边流值相等。   \n",
    "$\\therefore$我们可以删除$x$节点，把通过$x$节点相连的各节点直接相连，这样不改变原来的流值。但这样操作结束后，\n",
    "$G^{'}$变成$G$，其最大流$f_{maxG}$要大于等于$f_{maxG^{'}}$   \n",
    "矛盾！   \n",
    "所以$f_{maxG^{'}}=f_{maxG}$"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 26.2-3\n",
    "注：左边是残存网络，右边是更新的最大流。   \n",
    "第一轮：   \n",
    "<center class = \"half\">\n",
    "<img src = \"./images/26.2-3_11.svg\"  width = \"20%\" align = left><img src = \"./images/26.2-3_12.svg\"  width = \"20%\" align = right>\n",
    "</center>"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "第二轮：   \n",
    "<center class = \"half\">\n",
    "<img src = \"./images/26.2-3_21.svg\"  width = \"20%\" align = left><img src = \"./images/26.2-3_22.svg\"  width = \"20%\" align = right>\n",
    "</center>   "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "第三轮：   \n",
    "<center class = \"half\">\n",
    "<img src = \"./images/26.2-3_31.svg\"  width = \"20%\" align = left><img src = \"./images/26.2-3_32.svg\"  width = \"20%\" align = right>\n",
    "</center>   "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "第四轮：    \n",
    "残存网络s和t不可达，算法停止。右边是最终结果，最大流是23.   \n",
    "<center class = \"half\">\n",
    "<img src = \"./images/26.2-3_41.svg\"  width = \"20%\" align = left><img src = \"./images/26.2-3_32.svg\"  width = \"15%\" align = right>\n",
    "</center>"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "综上，最大流是23."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 26.3-1\n",
    "初始图：   \n",
    "<img src = \"./images/26.3-1_1.svg\"  width = \"40%\">\n",
    "\n",
    "增广路：s->1->6->t   \n",
    "<img src = \"./images/26.3-1_2.svg\"  width = \"40%\">\n",
    "\n",
    "增广路：s->2->8->t   \n",
    "<img src = \"./images/26.3-1_3.svg\"  width = \"40%\">\n",
    "\n",
    "增广路：s->3->7->t    \n",
    "<img src = \"./images/26.3-1_4.svg\"  width = \"40%\">   \n",
    "\n",
    "综上，最大匹配为3"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.10.2 (tags/v3.10.2:a58ebcc, Jan 17 2022, 14:12:15) [MSC v.1929 64 bit (AMD64)]"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "a166369db42c1466e2e3775def9041c304cd3bfe227c8b0f35b781bd0a6af835"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
